package com.company.tx2021;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main3 {
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        Map<String,Integer> map = new HashMap<>();
        String[][] data = new String[n][2];
        for (int i = 0; i < n; i++) {
            String temp = sc.next();
            if(!map.containsKey(temp)){
                map.put(temp,i);
                data[i][0] = temp;
                data[i][1] = String.valueOf(1);
            }else{
                int index = map.get(temp);
                int count = Integer.parseInt(data[index][1]) + 1;
                data[index][1] = String.valueOf(count);
            }
        }
        int num = 0;
        for (int i = 0;i < n;i++){
            if(data[i][0] != null){
                num++;
            }
        }
        String[][] data_cp = new String[num][2];
        int kx = 0;
        for (int i = 0;i < n;i++){
            if(data[i][0] != null){
                data_cp[kx][0] = data[i][0];
                data_cp[kx][1] = data[i][1];
                kx++;
            }
        }


        Arrays.sort(data_cp,(a,b) ->{
            if(a[1] != b[1]){
                return Integer.parseInt(b[1]) - Integer.parseInt(a[1]);
            }else{
                String s1 = a[0];
                String s2 = b[0];
                int len1 = s1.length();
                int len2 = s2.length();
                int i = 0,j = 0;
                while (i < len1 && j < len2){
                    if(s1.charAt(i) < s2.charAt(j)){
                        return 1;
                    }else if(s1.charAt(i) > s2.charAt(j)){
                        return -1;
                    }
                }
                if(i < j){
                    return 1;
                }else if(i > j){
                    return -1;
                }else {
                    return 0;
                }
            }

        });
//        for (int i = 0; i < kx; i++) {
//            System.out.print(data_cp[i][0]);
//            System.out.print(" ");
//            System.out.println(data_cp[i][1]);
//        }
//        System.out.println("------");
        for (int i = kx - 1 ; i > kx - 1 - k ; i--) {
            System.out.println(data_cp[i][0] + " " + data_cp[i][1]);
        }
        Arrays.sort(data_cp,(a,b) ->{
            if(a[1] != b[1]){
                return Integer.parseInt(a[1]) - Integer.parseInt(b[1]);
            }else{
                String s1 = a[0];
                String s2 = b[0];
                int len1 = s1.length();
                int len2 = s2.length();
                int i = 0,j = 0;
                while (i < len1 && j < len2){
                    if(s1.charAt(i) < s2.charAt(j)){
                        return 1;
                    }else if(s1.charAt(i) > s2.charAt(j)){
                        return -1;
                    }
                }
                if(i < j){
                    return 1;
                }else if(i > j){
                    return -1;
                }else {
                    return 0;
                }
            }

        });
//        System.out.println("---");
        for (int i = 0;i < k;i++){
            System.out.println(data_cp[i][0] + " " + data_cp[i][1]);
        }

    }
}
